package com.github.yangyishe.p200;

import java.util.Arrays;

/**
 * 135. 分发糖果
 * https://leetcode.cn/problems/candy/?envType=study-plan-v2&envId=top-interview-150
 * todo 效率较低, 待优化
 *
 * n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
 *
 * 你需要按照以下要求，给这些孩子分发糖果：
 *
 * 每个孩子至少分配到 1 个糖果。
 * 相邻两个孩子评分更高的孩子会获得更多的糖果。
 * 请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：ratings = [1,0,2]
 * 输出：5
 * 解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
 * 示例 2：
 *
 * 输入：ratings = [1,2,2]
 * 输出：4
 * 解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
 *      第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。
 *
 *
 * 提示：
 *
 * n == ratings.length
 * 1 <= n <= 2 * 104
 * 0 <= ratings[i] <= 2 * 104
 */
public class Problem135 {
    public static void main(String[] args) {
        int[] ratings={1,2,87,87,87,2,1};

        Problem135 problem135 = new Problem135();
        int candy = problem135.candy(ratings);
        System.out.println(candy);

    }

    public int candy(int[] ratings) {

        int[] candies=new int[ratings.length];
        candies[0]=1;
        int tempHighRatingIndex=0;
        for (int i = 1; i < ratings.length; i++) {
            if(ratings[i]>ratings[i-1]){
                candies[i]=candies[i-1]+1;
                tempHighRatingIndex=i;
            }else if(ratings[i]==ratings[i-1]){
                candies[i]=1;
                tempHighRatingIndex=i;
            }else{
                candies[i]=1;
                if(candies[i]==candies[i-1]){
                    for(int j=i-1;j>=tempHighRatingIndex;j--){
                        if(candies[j]==candies[j+1]){
                            candies[j]=candies[j]+1;
                        }
                    }
                }
            }
        }

        System.out.println("candies:"+ Arrays.toString(candies));

        int sumCandyCount=0;
        for (int candy : candies) {
            sumCandyCount+=candy;
        }

        return sumCandyCount;
    }
}
